//785. 判断二分图

//存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：
//不存在自环（graph[u] 不包含 u）。
//不存在平行边（graph[u] 不包含重复值）。
//如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
//这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。
//二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。
//如果图是二分图，返回 true ；否则，返回 false 。

// 如果给定的无向图连通，那么我们就可以任选一个节点开始，给它染成红色。随后我们对整个图进行遍历，将该节点直接相连的所有节点染成绿色，表示这些节点不能与起始节点属于同一个集合。我们再将这些绿色节点直接相连的所有节点染成红色，以此类推，直到无向图中的每个节点均被染色。
// 如果我们能够成功染色，那么红色和绿色的节点各属于一个集合，这个无向图就是一个二分图；如果我们未能成功染色，即在染色的过程中，某一时刻访问到了一个已经染色的节点，并且它的颜色与我们将要给它染上的颜色不相同，也就说明这个无向图不是一个二分图。
//class Solution {
//private:
//    static constexpr int UNCOLORED = 0;
//    static constexpr int RED = 1;
//    static constexpr int GREEN = 2;
//    vector<int> color;
//    bool valid;
//
//public:
//    void dfs(int node, int c, const vector<vector<int>>& graph) {
//        color[node] = c;
//        int cNei = (c == RED ? GREEN : RED);
//        for (int neighbor : graph[node]) {
//            if (color[neighbor] == UNCOLORED) {
//                dfs(neighbor, cNei, graph);
//                if (!valid) {
//                    return;
//                }
//            }
//            else if (color[neighbor] != cNei) {
//                valid = false;
//                return;
//            }
//        }
//    }
//
//    bool isBipartite(vector<vector<int>>& graph) {
//        int n = graph.size();
//        valid = true;
//        color.assign(n, UNCOLORED);
//        for (int i = 0; i < n && valid; ++i) {
//            if (color[i] == UNCOLORED) {
//                dfs(i, RED, graph);
//            }
//        }
//        return valid;
//    }
//};

//886. 可能的二分法

//给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
//给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和  bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

//class Solution {
//public:
//    bool dfs(int curnode, int nowcolor, vector<int>& color, const vector<vector<int>>& g) {
//        color[curnode] = nowcolor;
//        for (auto& nextnode : g[curnode]) {
//            if (color[nextnode] && color[nextnode] == color[curnode]) {
//                return false;
//            }
//            if (!color[nextnode] && !dfs(nextnode, 3 ^ nowcolor, color, g)) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
//        vector<int> color(n + 1, 0);
//        vector<vector<int>> g(n + 1);
//        for (auto& p : dislikes) {
//            g[p[0]].emplace_back(p[1]);
//            g[p[1]].emplace_back(p[0]);
//        }
//        for (int i = 1; i <= n; ++i) {
//            if (color[i] == 0 && !dfs(i, 1, color, g)) {
//                return false;
//            }
//        }
//        return true;
//    }
//};